1. Field of the Invention
The present invention relates generally to computer processes for interpolating input data which relates to data structures representing functional and structural aspects of physical objects or activities. More particularly, the present invention relates to computerized method for improving data resolution. A specific implementation of the present invention is described for a method for graphics image processing data analysis and resolution synthesis enhancements.
2. Description of Related Art
For many computer process applications, it is necessary to interpolate input data comprising source apparatus low resolution output data in order to achieve acceptable, usable, or improved results.
Representative data often presents a low resolution input data set that is a poor replication of the original source. The data presents something much less than a true-life rendering. Many types of source data can benefit by data resolution enhancement: computer image data, digital or analog video data, geographic data measured on a regular grid, vector field data, speech synthesis signals data, and the like.
As to more specific examples in the field of image processing--such as digital scanning, dot matrix printing, digital camera to video display conversion, WEBTV.TM. and other Internet provider data, JPEG computer image standards, CDROM, magnetic resonance imaging, interframe interpolation for analog video, and the like--the source of the imaging data often provides graphical image data (including bit mapped alphanumeric text images) which is of a relatively low resolution. The term "graphics" as used herein shall be understood to be generic for all forms of imaging. Therefore, output renderings made directly from the source data may be of a low quality.
Moreover, source images--such as JPEG photographs, Internet and WEBTV files--are often compressed using relatively high data loss compression algorithms to reduce memory storage requirements for the providers. Decompression algorithms applied when the data is retrieved from memory essentially interpolate the reduced data using simple linear interpolation techniques lacking the precision necessary to reproduce the original image faithfully.
In color printing, such as with laser or ink-jet dot matrix hard copy apparatus, it may be even simply a user preference to create a print with higher resolution than the source provides in order to provide a sharper, less grainy, smoother textured image to present an overall higher quality and artistic print.
Another example of a need for resolution enhancement is during use of an image video display where one is viewing an image but would like to zoom in for cropping before printing or merely to get a closer look at a particular detail within the original image.
Thus, there is a continuing need for methods of interpolating many types of low resolution data to a higher resolution.
Image processing is a fairly well developed science of modifying and analyzing pictures, graphics designs, and the like. See e.g., Introduction to Image Processing Algorithms, Benjamin M. Dawson, Byte Magazine, March 1987, pp. 169-186. A variety of different approaches to image interpolation have been proposed and used. Known manner colorimetry constructs and methods of multidimensional color space data interpolation are described in the literature, such as Principles of Color Technology, by Billmeyer and Saltzman, John Wiley & Sons, Inc., New York, publishers, copr. 1981 (2d ed.); Color Science: Concepts and Methods, Quantitative Data and Formula, by Wyszecki and Stiles, John Wiley & Sons, Inc., New York, publishers, copr. 1982 (2d ed.); and Fundamentals of Interactive Computer Graphics, Foley and Van Dam, Addison-Wesley Publishing Company.
B-spline interpolators, such as image picture element ("pixel") replication and bilinear interpolation, are well known in the art. The main concept of B-spline interpolation is to specify an interpolating function which approximates the original image by sampling across a range of the source image data. The interpolating function is defined on a continuous-valued parameter and may be evaluated at arbitrary points. The resulting values comprise the interpolated image pixels. An important requirement is that the interpolating function must pass through the known function values from the sampled data. The order in B-spline interpolation--2.sup.nd order, 3.sup.rd order. et seq.--refers to the maximum number of continuous derivatives that the interpolating function is required to have. Higher-ordered B-spline image interpolation results tend to look smoother and more continuous. Once the interpolating function has been obtained, still more computation is required to recover the desired output samples. Thus, the primary drawback is that complex, and thus costly, computation logic and data processing time is required.
In pixel replication, the interpolating function is piecewise constant. This means that each output pixel simply takes the value of the closest input pixel. Pixel replication tends to produce blocking (stair step edge renderings) or aliasing artifacts (undesirable spurious marks).
In bilinear interpolation, the interpolating function is piecewise linear; it may be obtained by connecting the known data samples with straight lines. This means that each output pixel may be computed as a linear combination of up to four input pixels. As a simple averaging algorithm, bilinear interpolation produces results that can be blurry.
Both pixel replication and bilinear interpolation perform satisfactorily for interpolating smooth textures. On the other hand, these single linear filter approaches tend to average image data across high-contrast boundaries like edges and rapid contrast change zones, causing a blocky or blurry printed result. Thus, these techniques are not especially effective in terms of edge and detail rendition.
Edge enhancement and smoothing non-linear algorithms are also known, particularly in the printing of alphanumeric text. The idea is to find edges (sharp tonal transitions, e.g, between an eye and the surrounding eye lid) in the source data and render them both continuous, rather than appearing to have steps, and sharp at the target resolution without blurring the values of pixels which lie on different sides of the edge. For example, U.S. Pat. No. 5,394,485 (Lowe et al., assigned to the common assignee of the present invention) discloses a Method and Apparatus for Smoothed Scaling of Facsimile Images. U.S. Pat. No. 5,270,728 (Lund et al., assigned to the common assignee of the present invention) teaches a pixel thinning methodology in a Raster Imaging Device Speed-Resolution Product Multiplying Method and Resulting Pixel Image Data Structure. U.S. Pat. No. 5,446,804 (Allebach et al., assigned to the common assignee of the present invention) discloses a method for Magnifying Digital Image[s] Using Edge Mapping where to magnify the image, an edge map is produced for certain image boundary conditions, generating one or more additional pixels in locations among the original pixels and expanding the distances between the pixels so that the resolution of the locations of the pixels becomes the same as the original pixels.
Conversely to pixel replication and bilinear interpolations, edge enhancement and smoothing algorithms may not be very effective in terms of improving smooth textures and transition zones.
There is a need for a data resolution enhancement methodology applicable to data representative of any data structures representing functional and structural aspects of physical objects or activities where subsets of the data can be extracted from the entire data set and interpolated.
In the application of the present invention for image data processing, there remains a specific need for a method of improving low resolution data which will improve the visual quality of the entire source image across the entire spectrum of content. The method for improving resolution should be effective for both graphics images and alphanumeric text.
Data filtering as used in the present invention is well known in the art. Texts such as Fundamentals of Digital Image Processing, by Anil Jain (copr. 19, Prentice Hall publishers) review such techniques. Specifically for printing technology, the use of data filtering is made in U.S. Pat. No. 5,313,287 (Barton et al., assigned to the assignee of the present invention).